﻿using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;

namespace PushBox
{
    /// <summary>
    /// 传统算法，广度优先搜索
    /// 逐层搜索，每一层释放上一层的搜索队列并开辟一个新的搜索队列，
    /// 优点，算法稳定
    /// 缺点，耗费空间，单线程搜索对于复杂的局面耗时很长
    /// </summary>
    class Auto : BaseAuto
    {
        public Auto(Action<string> handler) : base(handler)
        {
            //Backup(path);
        }

        private int Width;
        private int Depth;
        private const string path = "Auto.solve";

        public override List<int> Run(Game game)
        {
            var st = Stopwatch.StartNew();
            var paths = RunMain(game);
            st.Stop();

            var lines = new List<string> {
                $"关卡{game.Level}:",
                game.MapData
            };

            if(paths == null)
            {
                Info = string.Format("无解,搜索深度{0},队列峰值{1},耗时{2}", Depth, Width, st.Elapsed);
            }
            else
            {
                Info = string.Format("最优解{0}步,队列峰值{1},耗时{2}", paths.Count, Width, st.Elapsed);
                var str = string.Join("", paths.Select(x => x == 0 ? "左" : x == 1 ? "上" : x == 2 ? "右" : "下"));
                lines.Add(str);
            }
            lines.Add(Info);
            lines.Add(spLine);
            File.AppendAllLines(path, lines);

            this.handler?.Invoke(Info);
            return paths;
        }

        private List<int> RunMain(Game game)
        {
            Depth = 0;
            Width = 0;
            var state = new GameState(game);
            var visitedStates = new List<string> { state.ToString() };
            var states = new List<GameState> { state };

            while (true)
            {
                Depth++;
                if (!states.Any())
                {
                    return null;
                }

                if (states.Count > Width)
                {
                    Width = states.Count;
                }
                //this.handler?.Invoke(string.Format("深度{0},当前队列{1},队列峰值{2}", Depth, states.Count, Width));
                var newStates = new List<GameState>();
                foreach (var stt in states)
                {
                    for (var dir = 0; dir < 4; dir++)
                    {
                        if (stt.LastDir != -1 && !stt.HasPush && Math.Abs(stt.LastDir - dir) == 2)
                        {
                            continue;
                        }
                        var newState = stt.Move(dir);
                        if (newState != null)
                        {
                            var str = newState.ToString();
                            if(visitedStates.Contains(str))
                            {
                                continue;
                            }
                            if(newState.Check())
                            {
                                return newState.GetPaths();
                            }
                            visitedStates.Add(str);
                            if(!newState.IsDeath())
                            {
                                newStates.Add(newState);
                            }
                        }

                    }
                }
                states = newStates;
            }
        }

        public override void Stop()
        {

        }
    }
}